import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 5. 最长回文子串
 *
 * @auth 罗俊华
 * @Date 2022/7/31 4:02 下午
 */

public class LongestPalindrome {

    @Test
    public void test1() {

        Assert.assertEquals("aba", longestPalindrome("babad"));
    }

    @Test
    public void test2() {
        Assert.assertEquals("bb", longestPalindrome("cbbd"));
    }


    @Test
    public void test3() {
        Assert.assertEquals("a", longestPalindrome("a"));
    }

    @Test
    public void test4() {
        Assert.assertEquals("a", longestPalindrome("ac"));
    }

    @Test
    public void test5() {
        Assert.assertEquals("ccc", longestPalindrome("ccc"));


    }

    @Test
    public void test6() {
        Assert.assertEquals("aca", longestPalindrome("aacabdkacaa"));
    }

    Map<Character, List<Integer>> map = new HashMap<>();

    String max_result;

    String string;

    public String longestPalindrome(String s) {
        if (s.length() == 1) {
            return s;
        }
        max_result = "";
        string = s;
        find(0);
        if (max_result.equals("")) {
            return s.substring(0, 1);
        }
        return max_result;

    }

    void find(int index) {
        String s = string.substring(index);
        if (s.length() == 1) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(index);
            map.put(s.charAt(0), list);
            return;
        }

        find(index + 1);
        Character currentChar = s.charAt(0);

        List<Integer> subIndexList = map.get(currentChar);


        if (subIndexList != null) {

            for (Integer subIndex : subIndexList) {

                if (subIndex - index + 2 > max_result.length()) {
                    boolean notResult = false;
                    for (int i = index, j = subIndex; i < j; j--, i++) {
                        if (string.charAt(i) != string.charAt(j)) {
//                            map.computeIfAbsent(currentChar, ArrayList::new).add(index);
                            notResult = true;
                            break;
                        }
                    }
                    if (!notResult) {

                        String result = string.substring(index, subIndex + 1);
                        if (result.length() > max_result.length()) {
                            max_result = result;
                        }
//                        简单优化，既然更长的回文（距离当前index更远的字符）都找到了，那就没必要找比这个更短的回文了
                        break;
                    }
                }
            }

        }
        map.computeIfAbsent(currentChar, ArrayList::new).add(index);

    }

}
